There is known an approach of generating an intermediate shape called a recognition model as an approach
for generating a mesh for a given two-dimensional or three-dimensional shape. This method of creating a mesh via an intermediate shape is frequently used in various fields including mesh generation for analysis in a finite element method and surface rendering. In the case of a three-dimensional shape, a recognition model can be defined as a solid composed of only faces parallel to a coordinate plane and formed with multiple solids having vertexes with integer coordinate values, which are heaped so that an input three-dimensional model is imitated. Once this recognition model can be generated, it is possible, by decomposing the recognition model into unit polyhedrons in an integer space, to generate hexahedron unit elements, for example. By assigning the hexahedron unit elements inside an input model, a hexahedral mesh can be generated. FIG. 17 shows a recognition model (b) and a structured mesh (c) generated from a predetermined input three-dimensional shape (a) with a prior-art method.
The following is a listing of prior art document considered herein:    [1] Japanese Patent Application No. 2002-178068 by Yamada, Yoshizawa, Inoue and Doi.    [2] “Recognition Model Construction Approach without Self Interference for Generation of Hexahedral Mesh” by Yamada, Yoshizawa, Inoue and Doi; Collected Lecture Draft Papers for 2002 Annual Meeting of The Japan Society for Industrial and Applied Mathematics; September, 2002.    [3] “Development of Automatic Three-Dimensional Element Decomposition System Using Shape Recognition” by Hiroaki Takahashi et al.; Collected Papers of The Japan Society of Mechanical Engineers Book A) 59(569); pp. 279-285, 1993.    [4] “Automatic Block Decomposition Using Fuzzy Logic Analysis” by Reza Taghavi, 9th International Meshing Roundtable, pp. 187-192, 2000.
In prior-art methods [1] and [2] for providing the structured mesh shown in FIG. 17, calculation is performed by solving an integer programming problem using an integer programming problem solver, using the imitation level of an input shape as an objective function and a condition causing no intersection as a constraint condition. In the prior-art methods, the constraint condition is dynamically changed by finding any violation position (intersection position) in iterative calculation and successively adding a constraint condition for resolving the violation. This process is repeated, and when all the violations of the constraint condition have been resolved, the iterative calculation ends and a recognition model without a violation is generated. In this case, the recognition model without an intersection is necessarily a decomposable shape. Accordingly, a mesh can be generated without a fail for a recognition model generated with the prior-art approaches.
It is a necessary condition for a non-decomposable shape to have an intersection of edges or faces, but having an intersection is not a sufficient condition for being a non-decomposable shape. In consideration of this point, the prior-art methods [1] and [2] provide a constraint of excluding intersections even when a recognition model is of a decomposable shape, and this may cause a problem that a generated mesh is deformed too much. Furthermore, the above-mentioned strict constraint condition is applied to all the calculations, and this may cause an inconvenience that predictability for output results to be generated by calculation required for outputting a suitable and allowable recognition model is reduced.
That is, if a recognition model is determined to be of a non-decomposable shape only because it has any intersection, it is a too strict condition for generation of a recognition model that is always decomposable. Among actual multidimensional shapes, there are shapes in which there is an intersection but it is allowable.
In addition to the methods described above, the documents [3] and [4] also disclose a method for generating a structured mesh via a recognition model of an input three-dimensional shape. However, the prior-art methods in the documents [3] and [4] below are not sufficient from the viewpoint of secure generation of a decomposable recognition model.